package com.cskaoyan.javase.recursion._4hanoi;

/**
 * 相传在古印度的圣庙中,有一种被称之为汉诺塔（也叫河内塔，Hanoi）的游戏
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>1）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * 	1，每次只能移动一个圆盘
 * 	2，大盘一定在小盘之下
 * 提示：可将圆盘临时置于塔2，也可以将塔1的圆盘重新移回塔1，但都必须遵循上述两条规则
 * 问：当塔1上有N（N>=1）个圆盘时，最少要移动多少次？（注意是最少）
 * 用递归求解汉诺塔问题,假设最少需要f(N)步就可以完成N个圆盘的汉诺塔问题
 * 递归的思想是分解的思想,f(N)的汉诺塔问题，可以做如下分解：
 * 完成N个盘子的汉诺塔问题，必不可少的一步是：
 *      将最大的盘子从塔1到塔3，这时要求塔3是空的
 *      要求塔1上除了最大盘子外的所有盘子，都必须在塔2上
 * 所以需要：
 *      1，将塔1上除最大盘子外的所有盘子，全部从塔1移到塔2
 *      2.将最大的盘子从塔1到塔3
 *      3.将塔2除最大盘子外的所有盘子，全部从塔2移到塔3
 * 不论盘子有多少个，只要按照上述三步走，就能够完成汉诺塔问题，这就是分解
 * 所有f(N)的汉诺塔问题，分解成：
 *      1.f（N-1）
 *      2.1步
 *      3.f（N-1）
 * 但是上述分解不是无限制进行的
 * 因为当N=1时，f（N）= 1
 * 递归体：f（N） = f(N-1) + 1 + f(N-1)
 * 递归出口：f（1） = 1
 *
 * f(N)的通项公式：
 * f(N) + 1 = 2(f(N-1) + 1)
 * (f(N) + 1) / (f(N-1) + 1) = 2
 * f(N) + 1 = 2^n
 * f(N) = 2^n - 1
 *
 * @since 11:32
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoiRecursionSolution(10));
    }

    public static long hanoiRecursionSolution(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        // 递归体
        return hanoiRecursionSolution(n - 1) + 1 + hanoiRecursionSolution(n - 1);
    }
}
